[洛谷P1435]回文字串

发表于 | 分类于 ， | | 阅读次数:

题目

题目描述

回文词是一种对称的字符串。任意给定一个字符串，通过插入若干字符，都可以变成回文词。此题的任务是，求出将给定字符串变成回文词所需要插入的最少字符数。

比如 “Ab3bd”插入2个字符后可以变成回文词“dAb3bAd”或“Adb3bdA”，但是插入少于2个的字符无法变成回文词。

注：此问题区分大小写

输入格式

一个字符串(0<strlen<=1000)

输出格式

有且只有一个整数，即最少插入字符数

样例输入

1
Ab3bd

样例输出

1
2

来源

IOI2000第一题

题解

这里有个易错点，关于strlen函数的。

strlen()函数其实就是个计数器，它会从字符串开头，到终止符结束，最后返回结果。

但是，有些时候我们为了方便，会在读入字符串的时候使用scanf(“%s”,a+1)这时候，strlen(a)的返回值一定是0，因为a字符串的开头就是终止符，正确做法strlen(a+1)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char str[5001];
int n;
int f[5001][5001];

int main(){
    cin>>str+1;
    n=strlen(str+1);
    for(int len=1;len<=n;len++){
        for(int i=1;i<=n-len+1;i++){
            int j=i+len-1;
            if(str[i]==str[j])f[i][j]=f[i+1][j-1];
            else f[i][j]=min(f[i+1][j],f[i][j-1])+1;
        }
    }
    printf("%d",f[1][n]);
    return 0;
}